#define _CRT_SECURE_NO_WARNINGS   1

#include<iostream>
#include<string>
using namespace std;

using namespace std;
const int N = 1e5 + 10;
long long num[N], cnt = 0;

void downAdjust(int low, int high)
{
	int i = low, j = 2 * i;
	while (j <= high)
	{
		if (j + 1 <= high&&num[j + 1]>num[j]) 
			j = j + 1;
		if (num[j]>num[i])
		{
			swap(num[i], num[j]);
			i = j;
			j = 2 * i;
		}
		else break;
	}
}
void upAdjust(int low, int high){
	int i = high, j = i / 2;
	while (j >= low)
	{
		if (num[j]<num[i])
		{
			swap(num[j], num[i]);
			i = j;
			j = i / 2;
		}
		else break;
	}
}
int main()
{
	int  n;
	cin >> n;
	while (n--){
		string s;
		cin >> s;
		if (s == "push")
		{
			int x;
			cin >> x;
			num[++cnt] = x;
			upAdjust(1, cnt);
		}
		else if (s == "top")
		{
			if (cnt == 0) 
				cout << "empty" << endl;
			else 
				cout << num[1] << endl;
		}
		else
		{
			if (cnt == 0) 
				cout << "empty" << endl;
			else
			{
				cout << num[1] << endl;
				num[1] = num[cnt--];
				downAdjust(1, cnt);
			}
		}
	}
	return 0;
}

